"""
官方解法：
模拟栈
"""
from typing import List


class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        popped_idx = 0 
        for item in pushed:
            stack.append(item)
            while stack and stack[-1]==popped[popped_idx]:
                stack.pop()
                popped_idx +=1
        return len(stack)==0


if __name__=='__main__':
    sol=Solution()
    # pushed=[1,2,3]
    # poped=[2,1,3]
    # pushed=[1,2,3,4,5,6,7]
    # poped=[1,2,5,3,6,7,4]
    pushed=[1,2,3,4,5]
    poped=[4,5,3,2,1]
    
    res=sol.validateStackSequences(pushed,poped)
    print(res)
    pass